package com.kiven.quicksort;

//快速排序算法的实现
public class QuickSort {
	public static void main(String[] args) {
		/**
		 * 输入的参数是用空格结尾的，
		 *这里程序的输入函数控制为一行字符串，然后用逗号将字符串中的数据分割开来，也就是变量数组args[]中的第一个数，也就是所输入的用逗号分开的字符串，
		 *只要将这个字符串用逗号分割开，进行数据校验后的数组就是要进行快速排序的数组。
		 *
		*/
		System.out.println("请输入你要进行排序的数据，用逗号分开");
		for(String str: args) {
			System.out.println("您输入的数据是：");
			System.out.println(str);
		}
		
		/**
		 * @param qf 实例化变量，使用该变量是为了调用变量中的方法
		 */
		QuickSort qf = new QuickSort();
		/**
		 * 在参数控制中，所传给对象的参数是一个数组，也就是可以进来多个参数，前提是这些参数必须
		 * 用空格隔开，但是在这里为了控制参数的正确性，要进行排序的参数是用逗号隔开，在数组中相当于
		 * 只有一个值，但是这个值是一个字符串，该字符串即是要进行排序的数组
		 * 
		 * @param strNum 用来接收这个字符串
		 */
		String strNum = args[0];
		/**
		 * 将传进来的参数进行分割，然后保存在该数组中
		 * @param resourceNums 存储分割完的字符串数组
		 */
		String[] resourceNums = strNum.split(",");
		
		int[] oldNums;  //存储已经通过校验的数组
		
		/**
		 * 处理分割完的数组，然后对数组进行处理
		 * 对分割完的参数数组进行校验，检查数组中是否存在不合法的元素
		 */
		if(qf.checkNums(resourceNums)) {
			oldNums = new int[resourceNums.length];
			for(int i=0; i<resourceNums.length; i++) {
				oldNums[i] = Integer.parseInt(resourceNums[i]);
			}
			//对该数组进行排序的部分
			System.out.println("快速排序结果");
			qf.quickSort(oldNums, 0, oldNums.length);
			qf.printArrays(oldNums);
			 
			System.out.println("冒泡排序结果");
			qf.bubbleSort(oldNums);
			qf.printArrays(oldNums);
		}
		else {
			System.out.println("对不起，你输入的数据不合法，请重新输入");
		}
	}
	
	
	/**
	 * 该方法对数据进行校验处理，返回正确的数据数组
	 * @param strs 接受要进行校验的数组参数
	 * @return flag 返回该控制标记的值，根据它判断数组中的数据是否合法
	 */
	public boolean checkNums(String[] strs) {
		boolean flag = true;  //控制标记
		for(String str : strs) {
			//通过正则表达式对数组中的元素进行校验
			if(!str.matches("^[1-9][0-9]*")) {
				flag = false;
				break;
			}
		}
		return flag;
	}
	
	/**
	 * 冒泡排序算法
	 * 从小到大
	 * 
	 * 基本思想
	 * 	 设待排序的数组为R[left...right],利用穷比的方法，找出数组中最大的那个数，依此类推最后完成排序
	 * ①分解：
	 * 	对数组中的元素两两之间进行比较，找出进行一轮(总的要比较的轮数是：right-left)比较后最大的数，
	 *  然后将这个数与R[left](实现从大到小)或R[right](实现从小到大)进行交换，接着用同样的方法处理剩下的元素直到最后
	 * 	 
	 * @param oldNums 进行冒泡排序的数组
	 */
	public void bubbleSort(int[] oldNums) {
		int temp;  //用来临时存放数据的变量
		for(int i=0; i<oldNums.length; i++) {
			for(int j=i+1; j<oldNums.length; j++) {
				if(oldNums[i] > oldNums[j]) {
					temp = oldNums[j];
					oldNums[j] = oldNums[i];
					oldNums[i] = temp;
				}
			}
		}
	}
		
	/**
	 * 快速排序算法
	 * 从小到大
	 * 
	 * 基本思想
	 * 	设待排序的数组是R[left...right],利用分治法可以将快速排序的思想描速为：
	 * 
	 * ①分解：
	 * 在R[left...right]中任选一个记录作为基准(Pivot)，
     * 以此基准将当前无序区划分为左、右两个较小的子区间R[left..pivotpos-1)和R[pivotpos+1..right]，
     * 并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，
     * 右边的子区间中所有记录的关键字均大于等于pivot.key，
     * 而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。
     * 注意：
     * 划分的关键是要求出基准记录所在的位置pivotpos。
     * 划分的结果可以简单地表示为(注意pivot=R[pivotpos])：
     * R[left..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..right].keys
     * 其中left≤pivotpos≤right。
     * ②求解：
     * 　通过递归调用快速排序对左、右子区间R[left..pivotpos-1]和R[pivotpos+1..right]快速排序。
     * 
     * 在下面的方法中oldNums[left]作为pivotValue，将数组oldNums中大于pivotValue数放在右边，小于pivotValue的数放在左边
     * 中间就是pvotValues
     * 
	 * @param oldNums 进行快速排序的数组
	 * @param left 数组的第一个元素位置
	 * @param right 数组的长度
	 */
	  public void quickSort(int[] oldNums,int left,int right)   
	    {    
	       int i,j;  //存放left和right   
	       int pivotValue,temp;   
	       i = left;   
	       j = right;   
	       pivotValue = oldNums[left];   
	       while(true)   
	       {   
	           while((++i)<right-1 && oldNums[i]<pivotValue);  //从左边开始查找，找出数组中大于pivotValue的位置   
	           while((--j)>left && oldNums[j]>pivotValue);   //从右边开始查找，找出数组中小于pivotValue的位置
	           if(i>=j)   //从左右两边查找出的两个数的下标进行比较
	               break; 
	           /*
	            * 利用temp这个中间变量
	            * 将oldNums[i]与oldNums[j]之间的数进行交换
	            */
	           temp = oldNums[i];   
	           oldNums[i] = oldNums[j];   
	           oldNums[j] = temp;   
	       }   
	     
	       /*
	        * 将pivotValue的值与oldNums[j]的值交换
	        * 然后以oldNums为中点将数组分成两个部分
	        */
	       oldNums[left] = oldNums[j];   
	       oldNums[j] = pivotValue;   
	       
	       //数组的右半部分
	       if(left<j)   //j的位置如果大于left就意味着左半部分还存在未排序的数，紧接着用递归的方法继续调用
	         quickSort(oldNums,left,j);   
	     
	       //数组的左半部分
	       if(right>i)  //i的位置如果小于right就意味着右半部分还存在未排序的数，紧接着用递归的方法继续调用  
	         quickSort(oldNums,i,right);
	       
	     }   

	/**
	 * 输出数组
	 * @param is 进行输出的数组
	 */
	public void printArrays(int[] is) {
		for(int i: is) {
			System.out.println(i);
		}
	}
	
	
}
